#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
//https://leetcode.cn/problems/contiguous-array/


// class Solution {
// public:
//     int findMaxLength(vector<int>& nums) 
//     {
//         int n = nums.size();
//         vector<int> dp(n+1), hash(2*n + 1, -1);
//         int maxLen = 0;
//         for (int i = 0; i<n; i++)
//         {
//             if (nums[i] == 1)
//                 dp[i+1] = dp[i] + 1;
//             else
//                 dp[i+1] = dp[i] - 1;

//             int num = dp[i+1] + n;
//             if (hash[num] != -1 || num == n)
//             {
//                 if (maxLen < i - hash[num])
//                     maxLen = i - hash[num];
//             }
//             else 
//                 hash[num] = i;
//         }

//         return maxLen;
//     } 
// };

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> hash(2 * n + 1, -1);
        int maxLen = 0, dp = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 1)
                ++dp;
            else
                --dp;

            int num = dp + n;
            if (hash[num] != -1 || num == n)
            {
                if (maxLen < i - hash[num])
                    maxLen = i - hash[num];
            }
            else
                hash[num] = i;
        }

        return maxLen;
    }
};